#include <vector>

using namespace std;
class Solution
{
public:
    // 思路：将数字放到对应的位置上，比如1放到下标0的位置，2放到下标1的位置，依次类推。然后再遍历一遍数组，找到第一个位置不对的数字，其下标加1即为缺失的最小正整数。如果所有位置都正确，则缺失的最小正整数为数组长度加1。
    int firstMissingPositive(vector<int> &nums)
    {
        int n = nums.size();
        // 将数字放到对应的位置上
        for (int i = 0; i < n; ++i)
        {
            // 注意这里是while，因为交换过来的数字还需要继续放到对应的位置上
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) // nums[i]在范围内且不在正确的位置上
            {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i)
        {
            if (nums[i] != i + 1)
            {
                return i + 1;
            }
        }
        return n + 1;
    }
};